package com.kobeliu.entity;

/**
 * @Author: Kobe_Liu
 * @Date: 2021/12/14 10:02
 */

import java.util.*;

/**
 * 中等题 --- 课程表_1
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 *
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 *
 *     例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 *
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 *
 * 示例 2：
 *
 * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
 * 输出：false
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
 */

/**
 * 拓扑矩阵  把一个有向无环图 ===> 变成线性的链表 就是拓扑矩阵
 */
public class Demo_83_No207 {


    public boolean canFinish1(int numCourses, int[][] prerequisites) {
        //课号和对应得入度
        Map<Integer,Integer> inDegree = new HashMap<>();
        for (int i = 0; i < numCourses; i++) {
            inDegree.put(i,0);
        }
        //处理入度，和 对应得相关数组
        Map<Integer,List<Integer>> abj = new HashMap<>();
        for(int[] relate:prerequisites){
            int cur = relate[1];
            int next = relate[0];
            //添加入度
            inDegree.put(next,inDegree.get(next)+1);

            if(!abj.containsKey(cur)){
                abj.put(cur,new ArrayList<>());
            }
            //往依赖的课程list中添加一个next
            //把key上掉，list里面的课才有可能上
            abj.get(cur).add(next);
        }
        //把当前入度为零的放入q
        Queue<Integer> q = new LinkedList<>();
        for (int k:inDegree.keySet()) {
            if(inDegree.get(k)==0){
                q.offer(k);
            }
        }
        while(!q.isEmpty()){
            int poll = q.poll();
            //代表poll课上完了
            if(!abj.containsKey(poll)){
                //如果不存在，代表 出度/入度==0
                continue;
            }
            List<Integer> successList = abj.get(poll);

            for(int k:successList){
                inDegree.put(k,inDegree.get(k)-1);
                if(inDegree.get(k)==0){
                    q.offer(k);
                }
            }
        }

        // 4.遍历入队, 如果还有课程的入度不为0, 返回false
        for (int key : inDegree.keySet()) {
            if (inDegree.get(key) != 0) {
                return false;
            }
        }
        return true;
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 1.课号和对应的入度
        Map<Integer, Integer> inDegree = new HashMap<>();
        // 将所有的课程先放入
        for (int i = 0; i < numCourses; i++) {
            inDegree.put(i, 0);
        }
        // 2.依赖关系, 依赖当前课程的后序课程
        Map<Integer, List<Integer>> adj = new HashMap<>();

        // 初始化入度和依赖关系
        for (int[] relate : prerequisites) {
            // (3,0), 想学3号课程要先完成0号课程, 更新3号课程的入度和0号课程的依赖(邻接表)
            int cur = relate[1];
            int next = relate[0];
            // 1.更新入度
            inDegree.put(next, inDegree.get(next) + 1);
            // 2.当前节点的邻接表
            if (!adj.containsKey(cur)) {
                adj.put(cur, new ArrayList<>());
            }
            adj.get(cur).add(next);
        }

        // 3.BFS, 将入度为0的课程放入队列, 队列中的课程就是没有先修, 可以学的课程
        Queue<Integer> q = new LinkedList<>();
        for (int key : inDegree.keySet()) {
            if (inDegree.get(key) == 0) {
                q.offer(key);
            }
        }
        // 取出一个节点, 对应学习这门课程.
        // 遍历当前邻接表, 更新其入度; 更新之后查看入度, 如果为0, 加入到队列
        while (!q.isEmpty()) {
            int cur = q.poll();
            // 遍历当前课程的邻接表, 更新后继节点的入度
            if (!adj.containsKey(cur)) {
                continue;
            }
            List<Integer> successorList = adj.get(cur);

            for (int k : successorList) {
                inDegree.put(k, inDegree.get(k) - 1);
                if (inDegree.get(k) == 0) {
                    q.offer(k);
                }
            }
        }

        // 4.遍历入队, 如果还有课程的入度不为0, 返回false
        for (int key : inDegree.keySet()) {
            if (inDegree.get(key) != 0) {
                return false;
            }
        }
        return true;

    }
}
